package 热题100.二叉树.二叉树的中序遍历_94_简单;
/*
迭代法：用队列模拟，中序是左中右，
    循环停止条件：栈不为空或者当前节点不为空，因为栈为空可能是只有根节点有一个右节点，然后都是左节点，
    节点为空更好解释，就是有的节点没有右节点，那么重新判断的时候就是空。
    先一直往左遍历，遇到空就记录并出栈往右走一格，然后继续一直往左。

    左中右就是每一个节点都先看左，左没有了则记录左，再往右走一格，如果右没有则记录的是中
    如果右有，那么往右走一格然后一直往左走，左没有了就记录左，依次迭代。

    因为当前节点a的左节点b也是节点b的子节点的中间节点，所以每次查看
    左节点的时候也相当于看了中节点

    总的来说就是（判断后）一直往左，左没有了就记录，然后往右一格，（判断后）再继续往左，左没有了就记录。 判断：栈或者节点不为空

    前序：（判断后）先记录，右不为空就入栈，左不为空也入栈，这样出栈就是中 左 右 判断：栈不为空
* */


import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, node3, null);
        TreeNode root = new TreeNode(1, null, node2);
        List<Integer> ans = inorderTraversal(root);
        for (int t : ans){
            System.out.println(t);
        }
    }

    public static List<Integer> inorderTraversal(TreeNode root) {
        // 用于记录遍历的节点
        List<Integer> list = new ArrayList<>();
        if (root == null){
            return list;
        }
        TreeNode cur = root;
        // 用栈来模拟
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 栈不为空或者节点不为空
        while (cur != null || !stack.isEmpty()){
            // 如果节点不为空，就将节点放入栈中，并继续往左走
            if (cur != null){
                stack.offer(cur);
                cur = cur.left; // 左
            } else {
                // 节点为空 更新当前节点为栈顶节点
                cur = stack.pollLast();
                // 这里存在两种情况，一是记录的左节点a，二是当节点走到叶子节点之后右节点也为空
                // 那么此时栈中的节点是a的父节点也就是中间节点，记录的就是中节点
                list.add(cur.val); // 左/中
                cur = cur.right; // 右
            }
        }
        return list;
    }



//    public static List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> list = new ArrayList<>();
//        inorder(root, list);
//        return list;
//    }
//
//    public stat ic void inorder(TreeNode cur, List<Integer> list){
//        if (cur == null) return;
//        inorder(cur.left, list);
//        list.add(cur.val);
//        inorder(cur.right, list);
//    }
    public static class TreeNode{
        public TreeNode left;
        public TreeNode right;
        public int val;

        TreeNode(){};
        public TreeNode(int val, TreeNode left, TreeNode right){
            this.val = val;
            this.left = left;
            this.right = right;
        }
        public TreeNode(int val){
            this.val = val;
        }
    }



}

